package day_2022_7_to_8.day48;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @author haomin
 * @date 2022/08/25 00:31
 **/
public class Day39_3_Num95_generateTrees {
    class Solution {
        public List<TreeNode> generateTrees(int n) {
            if (n == 0) return new LinkedList<TreeNode>();
            return generate(1, n);
        }

        private List<TreeNode> generate(int start, int end) {
            List<TreeNode> allTrees = new ArrayList<>();
            if (start > end) {
                allTrees.add(null);
                return allTrees;
            }
            for (int i = start; i <= end; i++) {
                List<TreeNode> leftTrees = generate(start, i - 1);
                List<TreeNode> rightTrees = generate(i + 1, end);

                for (TreeNode left : leftTrees) {
                    for (TreeNode right : rightTrees) {
                        TreeNode cur = new TreeNode(i);
                        cur.left = left;
                        cur.right = right;
                        allTrees.add(cur);
                    }
                }
            }
            return allTrees;
        }
    }
}